home *** CD-ROM | disk | FTP | other *** search
/ Chip 2006 June / CHIP 2006-06.2.iso / program / freeware / Democracy-0.8.2.exe / xulrunner / python / BitTorrent / PiecePicker.py < prev    next >
Encoding:
Python Source  |  2006-04-10  |  4.6 KB  |  139 lines

  1. # The contents of this file are subject to the BitTorrent Open Source License
  2. # Version 1.0 (the License).  You may not copy or use this file, in either
  3. # source code or executable form, except in compliance with the License.  You
  4. # may obtain a copy of the License at http://www.bittorrent.com/license/.
  5. #
  6. # Software distributed under the License is distributed on an AS IS basis,
  7. # WITHOUT WARRANTY OF ANY KIND, either express or implied.  See the License
  8. # for the specific language governing rights and limitations under the
  9. # License.
  10.  
  11. # Written by Bram Cohen
  12.  
  13. from random import randrange, shuffle, choice
  14.  
  15.  
  16. class PiecePicker(object):
  17.  
  18.     def __init__(self, numpieces, config):
  19.         self.config = config
  20.         self.numpieces = numpieces
  21.         self.interests = [range(numpieces)]
  22.         self.pos_in_interests = range(numpieces)
  23.         self.numinterests = [0] * numpieces
  24.         self.have = [False] * numpieces
  25.         self.crosscount = [numpieces]
  26.         self.started = []
  27.         self.seedstarted = []
  28.         self.numgot = 0
  29.         self.scrambled = range(numpieces)
  30.         shuffle(self.scrambled)
  31.  
  32.     def got_have(self, piece):
  33.         numint = self.numinterests[piece]
  34.         self.crosscount[numint + self.have[piece]] -= 1
  35.         self.numinterests[piece] += 1
  36.         try:
  37.             self.crosscount[numint + 1 + self.have[piece]] += 1
  38.         except IndexError:
  39.             self.crosscount.append(1)
  40.         if self.have[piece]:
  41.             return
  42.         if numint == len(self.interests) - 1:
  43.             self.interests.append([])
  44.         self._shift_over(piece, self.interests[numint], self.interests[numint + 1])
  45.  
  46.     def lost_have(self, piece):
  47.         numint = self.numinterests[piece]
  48.         self.crosscount[numint + self.have[piece]] -= 1
  49.         self.numinterests[piece] -= 1
  50.         self.crosscount[numint - 1 + self.have[piece]] += 1
  51.         if self.have[piece]:
  52.             return
  53.         self._shift_over(piece, self.interests[numint], self.interests[numint - 1])
  54.  
  55.     def _shift_over(self, piece, l1, l2):
  56.         p = self.pos_in_interests[piece]
  57.         l1[p] = l1[-1]
  58.         self.pos_in_interests[l1[-1]] = p
  59.         del l1[-1]
  60.         newp = randrange(len(l2) + 1)
  61.         if newp == len(l2):
  62.             self.pos_in_interests[piece] = len(l2)
  63.             l2.append(piece)
  64.         else:
  65.             old = l2[newp]
  66.             self.pos_in_interests[old] = len(l2)
  67.             l2.append(old)
  68.             l2[newp] = piece
  69.             self.pos_in_interests[piece] = newp
  70.  
  71.     def requested(self, piece, seed = False):
  72.         if piece not in self.started:
  73.             self.started.append(piece)
  74.         if seed and piece not in self.seedstarted:
  75.             self.seedstarted.append(piece)
  76.  
  77.     def complete(self, piece):
  78.         assert not self.have[piece]
  79.         self.have[piece] = True
  80.         self.crosscount[self.numinterests[piece]] -= 1
  81.         try:
  82.             self.crosscount[self.numinterests[piece] + 1] += 1
  83.         except IndexError:
  84.             self.crosscount.append(1)
  85.         self.numgot += 1
  86.         l = self.interests[self.numinterests[piece]]
  87.         p = self.pos_in_interests[piece]
  88.         l[p] = l[-1]
  89.         self.pos_in_interests[l[-1]] = p
  90.         del l[-1]
  91.         try:
  92.             self.started.remove(piece)
  93.             self.seedstarted.remove(piece)
  94.         except ValueError:
  95.             pass
  96.  
  97.     def next(self, havefunc, seed = False):
  98.         bests = None
  99.         bestnum = 2 ** 30
  100.         if seed:
  101.             s = self.seedstarted
  102.         else:
  103.             s = self.started
  104.         for i in s:
  105.             if havefunc(i):
  106.                 if self.numinterests[i] < bestnum:
  107.                     bests = [i]
  108.                     bestnum = self.numinterests[i]
  109.                 elif self.numinterests[i] == bestnum:
  110.                     bests.append(i)
  111.         if bests:
  112.             return choice(bests)
  113.         if self.numgot < self.config['rarest_first_cutoff']:
  114.             for i in self.scrambled:
  115.                 if havefunc(i):
  116.                     return i
  117.             return None
  118.         for i in xrange(1, min(bestnum, len(self.interests))):
  119.             for j in self.interests[i]:
  120.                 if havefunc(j):
  121.                     return j
  122.         return None
  123.  
  124.     def am_I_complete(self):
  125.         return self.numgot == self.numpieces
  126.  
  127.     def bump(self, piece):
  128.         l = self.interests[self.numinterests[piece]]
  129.         pos = self.pos_in_interests[piece]
  130.         del l[pos]
  131.         l.append(piece)
  132.         for i in range(pos,len(l)):
  133.             self.pos_in_interests[l[i]] = i
  134.         try:
  135.             self.started.remove(piece)
  136.             self.seedstarted.remove(piece)
  137.         except ValueError:
  138.             pass
  139.